/*
    Copyright 2006-2011 Patrik Jonsson, sunrise@familjenjonsson.org

    This file is part of Sunrise.

    Sunrise is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 3 of the License, or
    (at your option) any later version.

    Sunrise is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Sunrise.  If not, see <http://www.gnu.org/licenses/>.

*/

/// \file
/// Contains the grid_base iterator classes.

// $Id$

// (This file is included automatically by grid.h)


/** Iterator that only traverses cells in the grid without descending
    into subgrids. This class is simple, so it doesn't need to inherit
    from iterator_impl. */
template < typename cell_data_type >
class mcrx::grid_base<cell_data_type>::local_iterator {
private:
  T_cell* c;
public:
  local_iterator (T_cell*cc): c (cc) {};
  operator const_local_iterator () {return const_local_iterator (c);};
  T_cell& operator*() const {assert (c); return *c;};
  T_cell* operator->() const {return c;};
  operator T_cell*() const {return c;};
  local_iterator& operator++ () { ++c; return *this;};
  local_iterator operator++ (int){ // postfix
    local_iterator i (*this); operator++ (); return i;};
  bool operator== (const local_iterator& i) const {return c == i.c;};
  bool operator!= (const local_iterator& i) const {return c != i.c;};
};

/** Const iterator that only traverses cells in the grid without
    descending into subgrids. This class is simple, so it doesn't need
    to inherit from iterator_impl. */
template < typename cell_data_type >
class mcrx::grid_base<cell_data_type>::const_local_iterator {
private:
  const T_cell* c;
public:
  const_local_iterator (const T_cell*cc): c (cc) {};
  const T_cell& operator*() const {assert (c); return *c;};
  const T_cell* operator->() const {return c;};
  operator const T_cell*() const {return c;};
  const_local_iterator& operator++ () { ++c; return *this;};
  const_local_iterator operator++ (int){ // postfix
    const_local_iterator i (*this); operator++ (); return i;};
  bool operator== (const const_local_iterator& i) const {return c == i.c;};
  bool operator!= (const const_local_iterator& i) const {return c != i.c;};
};

/** Private base class for the iterator classes.  Since the iterator
 classes have a somewhat complex implementation to go down into the
 sub grids, we collect this into a private base class.  Unfortunately,
 because of the difference in const-ness and because they need to call
 functions of grid_base and grid_cell, we have to make it a template.
 At least we only have to write the functions once, even if we get
 code bloat. */
template < typename cell_data_type >
template <typename TT_grid, typename TT_cell>
class mcrx::grid_base<cell_data_type>::iterator_impl  {
private:
  bool operator== (const iterator_impl& i) const {return c == i.c;};
  bool operator!= (const iterator_impl & i) const {return c != i.c;};
protected:
  TT_grid* g;
  TT_cell* c;
  // these are implementations the derived classes use,
  // they increment *this.
  void prefix_increment_stepdown ();
  void recursive_stepup ();
  void recursive_stepdown ();

  iterator_impl (); ///< Constructor not defined.
  iterator_impl (TT_grid* gg, TT_cell* cc): g (gg), c (cc) {};
  /** This constructor is used to ensure that we step down to a leaf
      cell, is used by begin () */
  explicit iterator_impl (TT_cell* cc): g (cc->host_grid()), c (cc) {
    recursive_stepdown ();};
};


// *** class iterator ***

/** Iterator that goes down into sub grids to find leaf cells. The
    traversal is done in a depth-first fashion and is deterministic,
    so it's used to collect coll data into tables when saving to
    files, etc.  An iterator can be converted to a local_iterator, but
    not vice versa since a local_iterator can point to a non-leaf cell
    which is invalid for an iterator. */
template < typename cell_data_type >
class mcrx::grid_base<cell_data_type>::iterator :
  public iterator_impl<T_grid, T_cell> {
public:
  iterator (T_grid*gg, T_cell*cc) :
    iterator_impl<T_grid, T_cell> (gg, cc) {};
  explicit iterator (T_cell*cc) : 
    iterator_impl<T_grid, T_cell> (cc) {};

  operator const_iterator () {return const_iterator (this->g, this->c);};

  T_cell& operator*() const { assert (this->c); return *this->c;};
  T_cell* operator->() const {return this->c;};
  operator T_cell*() const {return this->c;};
  iterator& operator++ () {
    this->prefix_increment_stepdown (); return *this;};
  iterator operator++ (int){ // postfix
    iterator i (*this); operator++ (); return i;};
  bool operator== (const iterator& i) const {return this->c == i.c;};
  bool operator!= (const iterator& i) const {return this->c != i.c;};
};


// *** class const_iterator ***

/** Const iterator that goes down into sub grids to find leaf cells. */
template < typename cell_data_type >
class mcrx::grid_base<cell_data_type>::const_iterator :
  public iterator_impl<const T_grid, const T_cell> {
public:
  const_iterator (const T_grid*gg, const T_cell*cc):
    iterator_impl<const T_grid, const T_cell> (gg, cc) {};
  explicit const_iterator (const T_cell*cc): 
    iterator_impl<const T_grid, const T_cell> (cc) {};
  const T_cell& operator*() const {assert (this->c); return *this->c;};
  const T_cell* operator->() const {return this->c;};
  operator const T_cell*() const {return this->c;};
  const_iterator& operator++ () {
    this->prefix_increment_stepdown (); return *this;};
  const_iterator operator++ (int){ // postfix
    const_iterator i (*this); operator++ (); return i;};
  bool operator== (const const_iterator& i) const {return this->c == i.c;};
  bool operator!= (const const_iterator& i) const {return this->c != i.c;};
};


// *** grid_base::iterator_impl methods ***

template < typename cell_data_type >
template <typename TT_grid, typename TT_cell>
void
mcrx::grid_base<cell_data_type>::iterator_impl<TT_grid, TT_cell>::
prefix_increment_stepdown () {
  // the first thing we do is to increment the cell pointer
  // however, if we are not pointing to a leaf cell it's because the
  // cell has been refined after we pointed to it.  In that case, we
  // do not increment the cell pointer but rather just step down.
  if (c->is_leaf())
    ++c;

  if (c == g->lend ()) {
    // if we are at the end of the cell counter we might have to step
    // up in the hierarchy
    recursive_stepup();
  }
  else
    // we are pointing at a cell, see if it's refined and we need to
    // step down
    recursive_stepdown ();
}
  
template < typename cell_data_type >
template <typename TT_grid, typename TT_cell>
void
mcrx::grid_base<cell_data_type>::iterator_impl<TT_grid, TT_cell>::
recursive_stepup ()
{
  // step up into the parent cell, if we have one
  if (TT_cell*pc = g->parent_cell()) {
    c = pc;
    g = c->host_grid();
    ++c;

    if (c == g->lend()) {
      // We are at the end of this grid as well, so now we need to
      // recurse in case we need to step up again
      recursive_stepup();
    }
    else 
      // We are now pointing at a cell that may or may not be subdivided
      recursive_stepdown ();
  }
  else {
    // if we don't have a parent cell we should be pointing at the
    // top-level end (), so we just double check.
    assert(c==g->lend());
  }
}


// Steps down until it finds a leaf cell
template < typename cell_data_type >
template <typename TT_grid, typename TT_cell>
void
mcrx::grid_base<cell_data_type>::iterator_impl<TT_grid, TT_cell>::
recursive_stepdown ()
{
  assert (c != g->lend());

  if (!c->is_leaf()) {
    // this is cell is also subdivided, continue
    *this = c->sub_grid()->begin();
    recursive_stepdown ();
  }

  // we are finally pointing at a leaf cell, return
}

